第 K 条最小指令

Bob 站在单元格 (0, 0) ，想要前往目的地 destination ：(row, column) 。他只能向 右 或向 下 走。你可以为 Bob 提供导航 指令 来帮助他到达目的地 destination 。

指令用字符串表示，其中每个字符：

  • ‘H’ ，意味着水平向右移动
  • ‘V’ ，意味着竖直向下移动
    能够为 Bob 导航到目的地 destination 的指令可以有多种，例如，如果目的地 destination 是(2, 3)，”HHHVV” 和 “HVHVH” 都是有效 指令 。

然而，Bob 很挑剔。因为他的幸运数字是 k，他想要遵循 按字典序排列后的第 k 条最小指令 的导航前往目的地 destination 。k 的编号 从 1 开始 。

给你一个整数数组 destination 和一个整数 k ，请你返回可以为 Bob 提供前往目的地 destination 导航的 按字典序排列后的第 k 条最小指令 。

示例 1：

ex1 (1)

1
2
3
4
输入：destination = [2,3], k = 1
输出："HHHVV"
解释：能前往 (2, 3) 的所有导航指令 按字典序排列后 如下所示：
["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].

示例 2：

ex2 (1)

1
2
输入：destination = [2,3], k = 2
输出："HHVHV"

示例 3：

ex3 (1)

1
2
输入：destination = [2,3], k = 3
输出："HHVVH"

提示：

  • destination.length == 2
  • 1 <= row, column <= 15
  • 1 <= k <= nCr(row + column, row)，其中 nCr(a, b) 表示组合数，即从 a 个物品中选 b 个物品的不同方案数。

代码：

46%85%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    public String kthSmallestPath(int[] destination, int k) {
        int h=destination[1];
        int v=destination[0];

        int[][] m=f2(h,v);

        return str(m,h,v,k);
    }
    public int[][] f2(int h,int v)
    {
        int[][] m=new int[h+1][v+1];
        for(int i=0;i<=h;i++)
        {
            for(int j=0;j<=v;j++)
            {
                if(j==0||i==0)
                    m[i][j]=1;
                else{
                    m[i][j]=m[i-1][j]+m[i][j-1];
                }
            }
        }

        return m;
    }
    public String str(int[][] m, int h, int v, int k)
    {
        int sum=0;
        if(v==1)
        {
            return markstr(h,h+v-k+1);
        }
        if(v>1)
            for (int i = 0; i <= h; i++) {
                int j = v - 1;
                //int vnum = j;
                sum += m[i][j];
                if(sum>=k)
                {
                    if(j==1)
                    {
                        String s1=markstr(h-i,h-i+1);
                        String s2=markstr(i,sum-k+1);
                        return s1+s2;
                    }
                    else{
                        String s1=markstr(h-i,h-i+1);
                        String s2=str(m,i,v-1,k-(sum-m[i][j]));
                        return s1+s2;
                    }
                }
                //break;
            }
        return "";
    }
    public String markstr(int h,int index)
    {
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<h+1;i++)
        {
            if(i==index-1)
                sb.append('V');
            else
                sb.append('H');
        }
        return sb.toString();
    }
}